Public key cryptography is used to permit secure communication between a pair of correspondents and to permit authentication of a message originating at one of the correspondents. In a public key cryptosystem each correspondent utilizes a private key and a public key related to the private key by a mathematical function. The mathematical function presents a “difficult” mathematical problem to ensure that a private key of a party cannot be obtained from the corresponding public key. Such problems include the difficulty in factoring the product of two large primes, as used in RSA cryptosystems, and the intractability of the discrete log problem over a finite field as used in the digital signature algorithm (DSA). Discrete log systems are widely used and a particular adaptation of such a system makes use of points of an elliptic curve defined over a finite field. Such systems, referred to as elliptic curve cryptosystems (ECC), offer high levels of security at smaller key sizes than other systems.
Where messages are to be exchanged securely, the public and private keys are used in particular protocols referred to generally as key agreement protocols to establish a shared key between the correspondents without disclosing the respective private keys. The shared key can then be used to encrypt and decrypt messages between the correspondents.
Elliptic curve public-key key agreement protocols typically include the following steps:                Key contributions. Each party randomly generates a short-term (ephemeral) public key, from a private key that is a random integer and a seed point to provide a point representing the ephemeral public key and communicates the corresponding ephemeral public key to the other party (but not the private key). In addition, it may communicate its long-term static public key.        Key establishment. Each party computes the shared key based on the static and ephemeral keys it received from the other party and based on the static and ephemeral private keys it generated itself. Due to the properties of the elliptic curve, both parties arrive at the same shared key.        Key authentication. Each party verifies the authenticity of the long-term static key of the other party, to obtain evidence that the only party that may be capable of computing the common key is, indeed, its perceived communicating party.        Key confirmation. Each party evidences possession of the common key to the other party, usually by communicating a message authentication check value over the strings corresponding to the key contributions communicated by either party. This confirms to each party the true identity of the other party and proves that that party successfully computed the common key. This step may be done as part of the key agreement protocol or subsequently through the use of the shared keys.        
The key authentication step is typically carried out independently of the other protocol steps described above and usually involves checking the validity of a certificate that vouches for the authenticity of the binding between a party and its private key by means of the corresponding public key. The separate key authentication step allows more flexibility (e.g., in the use of a certificate), but comes at significant cost, since the online computational cost of the key agreement protocol is dominated by the sum of the cost of the key authentication step and the cost of the key computation during the key establishment step.
The certificate is essentially a trusted party's signature of the public key of the correspondent together with the other information such as the name of the issuing party and the name of the certificate holder. In an ECC system, signatures are usually performed and verified using the ECDSA protocol although other signature protocols may be used. By way of example, ECDSA signature generation operates on the domain parameters of the ECC, a private key d, and a message m which, in the context of a certificate, will include the public key of the correspondent. The outputs are the signature (r,s), where the signature components r and s are integers, and proceeds as follows.                1. Select a random integer k εR [1, n−1], n being one of the domain parameters.        2. Compute kG=(x1,y1) and convert x1 to an integer x1, where G is a point on an elliptic curve E and is one of the domain parameters.        3. Compute r= x1 mod n, wherein if r=0, then go back to step 1.        4. Compute e=H(m), where H denotes a cryptographic hash function whose outputs have a bit length no more than that of n (if this condition is not satisfied, then the outputs of H can be truncated).        5. Compute s=k−1(e+α r) mod n, where a is a long term private key of the signer. If s=0, then go back to step 1.        6. Output the pair (r, s) as the ECDSA signature of the message m.        
ECDSA signature verification operates on several domain parameters, a long term public key Q where Q=αG, the message m, and the signature (r, s) derived above. ECDSA signature verification outputs a rejection or acceptance of the signature, and proceeds as follows.                1. Verify that r and s are integers in the interval [1,n−1]. If any verification fails then a rejection is returned.        2. Compute e=H(m).        3. Compute w=s−1 mod n.        4. Compute μ1=ew mod n and μ2=rw mod n.        5. Compute R=μ1G+μ2Q=s−1 (eG+rQ) (from 3 and 4 above)        6. If R=∞ then the signature is rejected.        7. Convert the x-coordinate x1 of R to an integer x1; compute v= x1 mod n.        8. If v=r then the signature is accepted, if not then the signature is rejected.        
It will be appreciated that other signature generation and verification steps may be used such as ECGDSA and that certain steps to confirm the integrity of the signature are sometimes omitted.
Therefore, to authenticate the public key of the correspondent i.e. the message m which contains the public key of the correspondent and other information it is necessary to verify the signature on the certificate.
Subsequent to authentication, it is usual to confirm that the key of each party is indeed the same. During execution of a key agreement protocol between two parties A and B, party A establishes the key KA, while party B establishes the key KB. Key confirmation consists of A evidencing knowledge of KA to B by conveying some quantity ƒ(KA), where ƒ is some publicly known function, to B, who will compare this to his own computed value ƒ(KB) and accept only if these values match (and vice versa). The function ƒ is such that if ƒ(KA)=ƒ(KB), then with overwhelming probability KA=±KB and a common key has been established.
As noted above, the key authentication step adds significant computational load to the key agreement protocol. It is therefore an object of the present invention to obviate or mitigate the above disadvantages.